//package com.lab303.powerproject.util;//请用utf8进行编译：-encoding utf8
//import java.util.*;
//import java.util.stream.Collectors;//该类自java-8引入，如果编译环境不支持java-8或以上环境，请删掉本行及main方法重新编译
//
//
///**
// *   使用约定：
// *   使用构造方法new一个对象之后，用addEdge方法来添加边，所以边添加完成后，用getResult方法计算。
// *   用getResult方法计算后，不可以再添加边，如果需要请再new一个对象重新一一加边再次计算；
// *   但可以多次调用getResult方法查看结果，多次调用getResult方法返回值均相同。
// *   查看某个具体节点的分配策略，使用query方法。
//*/
//
//public class MinCost {
//
//    private static Comparator<int[]> cmp = new Comparator<int[]>() {
//        @Override
//        public int compare(int[] p1, int[] p2) {
//            return p1[0] - p2[0];
//        }
//    };
//
//    public static class Edge {
//        int cap;
//        final int to, cost, rev;
//        final boolean positive;
//
//        Edge(int to, int cap, int cost, int rev, boolean positive) {
//            this.to = to;
//            this.cap = cap;
//            this.cost = cost;
//            this.rev = rev;
//            this.positive = positive;
//        }
//    }
//
//    private static final int INF = 0x3f3f3f3f;
//
//    private final int n;
//    private int result;
//    private final List<List<Edge>> G;
//
//    //用来检查节点是否合法的辅助方法
//    private boolean validNode(int node) {
//        return 0 <= node && node < n;
//    }
//
//    /**
//     * @return 图的节点个数
//     */
//    public int nodeNum() {
//        return n;
//    }
//
//    /**
//     * 构造方法
//     * @exception IllegalArgumentException 如果节点的个数小于两个
//     * @param n 图的节点个数
//     */
//    public MinCost(int n) {
//        if (n < 2) {
//            throw new IllegalArgumentException("节点的个数应大于等于两个");
//        }
//
//        this.n = n;
//        result = -INF;
//        G = new ArrayList<>(n);
//        for (int i = 0; i < n; i++) {
//            G.add(new ArrayList<>());
//        }
//    }
//
//    /**
//     * 为这个图添加一条边，请在用getResult方法计算前添加，用getResult方法计算后不允许再加边，
//     * 如果需要在另一个图上计算，请new另外一个对象重新加边进行计算。
//     * @param from 该边的出发节点
//     * @param to 该边的进入节点
//     * @param cap 该边的最大容量
//     * @param cost 该边单位流的费用
//     * @exception IllegalStateException 如果在调用getResult方法计算之后调用此方法
//     * @exception IllegalArgumentException from和to的值不在[0, n)的范围内，或cap和cost的值为负
//     */
//    public void addEdge(int from, int to, int cap, int cost) {
//        if (result != -INF) {
//            throw new IllegalStateException("进行运算之后不能重新加边，请用一个新的对象重新加边计算");
//        }
//        if (!validNode(from) || !validNode(to)) {
//            throw new IllegalArgumentException("from和to的值应在[0, n)之间");
//        }
//        if (cap < 0 || cost < 0) {
//            throw new IllegalArgumentException("cap和cost的值应为非负值");
//        }
//        // 加一条容量为0的边没有意义，所以直接返回
//        if (cap == 0) {
//            return;
//        }
//
//        G.get(from).add(new Edge(to, cap, cost, G.get(to).size(), true));
//        G.get(to).add(new Edge(from, 0, -cost, G.get(from).size() - 1, false));
//    }
//
//    /**
//     * 添加所有的边后，调用此方法来计算最小费用流，可多次调用，但调用之后请勿再加边
//     * @param source 源点
//     * @param dest 汇点
//     * @param flow 要发送的流的大小
//     * @return 从source发送flow大小的流到dest的最小费用，如果无法发送这么大的流返回-1
//     * @exception IllegalArgumentException source和dest不在[0, n)之间，或flow为负
//     */
//    public int getResult(int source, int dest, int flow) {
//        if (result == -INF) {
//            result = solve(source, dest, flow);
//        }
//        return result;
//    }
//
//    //使用Dijkstra算法的、在残存网络上寻找增广路径的最小费用流算法
//    private int solve(int source, int dest, int flow) {
//        if (!validNode(source) || !validNode(dest)) {
//            throw new IllegalArgumentException("source和dest的值应在[0, n)之间");
//        }
//        if (flow < 0) {
//            throw new IllegalArgumentException("flow的值应为非负值");
//        }
//
//        PriorityQueue<int[]> que = new PriorityQueue<>(cmp);
//        int[] dist = new int[n], h = new int[n], prevv = new int[n], preve = new int[n];
//        int ans = 0;
//        while (flow > 0) {
//            //用Dijkstra算法在残存网络上寻找一条费用最小的增光路经
//            Arrays.fill(dist, INF);
//            dist[source] = 0;
//            for (que.add(new int[] { 0, source }); que.size() > 0;) {
//                int[] p = que.poll();
//                int d = p[0], v = p[1];
//                if (d > dist[v]) {
//                    continue;
//                }
//                for (int i = 0, size = G.get(v).size(); i < size; i++) {
//                    Edge e = G.get(v).get(i);
//                    if (e.cap > 0 && dist[e.to] > dist[v] + h[v] - h[e.to] + e.cost) {
//                        dist[e.to] = dist[v] + h[v] - h[e.to] + e.cost;
//                        que.add(new int[] { dist[e.to], e.to });
//                        prevv[e.to] = v;
//                        preve[e.to] = i;
//                    }
//                }
//            }
//            //如果无法到达目标节点，返回-1表示无解
//            if (dist[dest] >= INF) {
//                return -1;
//            }
//            for (int v = 0; v < n; v++) {
//                h[v] += dist[v];
//            }
//            int d = flow;
//            for (int v = dest; v != source; v = prevv[v]) {
//                d = Math.min(d, G.get(prevv[v]).get(preve[v]).cap);
//            }
//            flow -= d;
//            ans += d * h[dest];
//            for (int v = dest; v != source; v = prevv[v]) {
//                Edge e = G.get(prevv[v]).get(preve[v]);
//                e.cap -= d;
//                G.get(v).get(e.rev).cap += d;
//            }
//        }
//        return ans;
//    }
//
//    /**
//     * 在getResult方法调用后，用此方法进行某个节点分配策略的查询
//     * @param node 要查询的节点
//     * @return 分配的策略，对于List中每个int[]，下标0存储发出流的目标节点，下标1存储发出的流的大小
//     * @exception IllegalStateException 在调用getResult方法进行计算之前调用本方法
//     */
//    public List<int[]> query(int node) {
//        if (result == -INF) {
//            throw new IllegalStateException("必须先执行getResult方法进行计算再调用本方法进行查询");
//        }
//
//        List<int[]> ans = new ArrayList<>();
//        for (Edge e : G.get(node)) {
//            Edge revEdge = G.get(e.to).get(e.rev);
//            if (e.positive && revEdge.cap > 0) {
//                ans.add(new int[] { e.to, revEdge.cap });
//            }
//        }
//        return ans;
//    }
//
//
//    /**
//     *  main方法用来测试，测试用例以这种格式给出：
//     *  边的个数m 节点个数n 流的大小f 源的编号s 汇的编号t
//     *  之后有m行，每行以如下格式给出：
//     *  边的出发点 边的进入点 边的最大容量 边的单位流费用
//    */
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int m = sc.nextInt(), n = sc.nextInt(), f = sc.nextInt(), source = sc.nextInt(), dest = sc.nextInt();
//        MinCost s = new MinCost(n);
//        for (int i = 0; i < m; i++) {
//            s.addEdge(sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt());
//        }
//        System.out.println(s.getResult(source, dest, f));
//        System.out.println(s.query(0).stream().map(Arrays::toString).collect(Collectors.joining(", ")));
//        sc.close();
//    }
//}